package Test;

import java.util.Arrays;

public class TestHeap {
    public int[]elem;
    public int usedsize;

    public TestHeap() {
        this.elem = new int[10];
    }

    public void initElem(int[]array){
        for (int i = 0; i <array.length ; i++) {
            this.elem[i]=array[i];
            usedsize++;
        }
    }

    public void createHeap(){
        for (int parent=(usedsize-1-1)/2;parent>=0;parent--){
            sifDown(parent,usedsize);
        }
    }

    private void sifDown(int parent,int usedsize){
        int child=parent*2+1;
        while(child<usedsize){
            if(child+1<usedsize&&elem[child]<elem[child+1]){
                child++;
            }
            if(elem[child]>elem[parent]){
                swap(elem,parent,child);
                parent=child;
                child=child*2+1;
            }else{
                break;
            }
        }
    }

    private void swap(int[]elem,int parent,int child){
        int tmp=elem[parent];
        elem[parent]=elem[child];
        elem[child]=tmp;
    }

    public void siftUp(int child){
        int parent=(child-1)/2;
        while(parent>=0){
            if(elem[parent]<elem[child]){
                swap(elem,parent,child);
                child=parent;
                parent=(parent-1)/2;
            }else {
                break;
            }
        }
    }

    public void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedsize]=val;
        siftUp(usedsize);
        usedsize++;
    }

    public int poll(){
        if(isEmpty()){
            return -1;
        }
        int val=elem[usedsize-1];
        swap(elem,0,usedsize-1);
        sifDown(0,usedsize-1);
        usedsize--;
        return val;
    }


    public void heapSort(){
        int end=usedsize-1;
        while(end>0){
            swap(elem,0,end);
            sifDown(0,end);
            end--;
        }
    }

    public boolean isFull(){
        return usedsize== elem.length;
    }

    public boolean isEmpty(){
        return usedsize==0;
    }

}
